package gold.gold05;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 *
 */
public class S1621交换和 {
    /**
     * 32, 感觉这种题目偏向于是一种想法, 而不是固定的算法。
     * 这个两个数值之间的差值可以通过先计算两个和之后算出来的。
     * 已排序的数列, 所以用Arrays.binarySearch()看看。
     * 用双指针更快, 毕竟排序了。
     */
    public int[] findSwapValues(int[] array1, int[] array2) {
        int sum1 = 0;
        int sum2 = 0;
        Arrays.sort(array2);
        Arrays.sort(array2);
        for(int i: array1) sum1 += i;
        for(int i: array2) sum2 += i;
        // array2比array1多diff, 交换的数字, array1中的要比array2中的大diff/2
        int diff = sum2 - sum1;
        if((diff & 1) == 1) return new int[0];// 注意取&操作优先级低于==。
        diff = diff >> 1; // 这个diff可能是负数
        for(int i: array1){
            if(Arrays.binarySearch(array2, i + diff) >= 0){
                return new int[]{i, i + diff};
            }
        }
        return new int[0];
    }

    /**
     * 双指针
     */
    public int[] findSwapValues2(int[] array1, int[] array2) {
        int sum1=0,sum2=0;
        for(int i:array1) sum1+=i;
        for(int i:array2) sum2+=i;
        int d=sum1-sum2;
        Arrays.sort(array1);
        Arrays.sort(array2);
        int i=0,j=0;
        while(i<array1.length&&j<array2.length) {
            if((array1[i]-array2[j])*2==d) return new int[] {array1[i],array2[j]};
            else if((array1[i]-array2[j])*2<d) i++;
            else j++;
        }
        return new int[] {};
    }

    /**
     * 用一个set存储array2, 然后在a2中搜索对应的值, 这个检索方式也快。
     */
    public int[] findSwapValues3(int[] a1, int[] a2) {
        int suma = 0, sumb = 0;
        Set<Integer> sb = new HashSet<>();
        int lena = a1.length, lenb = a2.length;

        for(int i = 0; i < lena; i++){
            suma += a1[i];
        }
        for(int i = 0; i < lenb; i++){
            sumb += a2[i];
            sb.add(a2[i]);
        }
        // 如果是 suma 比较大，那么dis就是负的。
        // 这里细节 sumb - suma
        int dis = sumb - suma;
        if(dis % 2 == 1) return new int[]{};
        dis /= 2;

        for(int i = 0; i < lena; i++){
            if(sb.contains(a1[i] + dis)) {
                return new int[]{a1[i], a1[i] + dis};
            }
        }
        return new int[]{};
    }

}
